package com.platform.modules.alg.alglib.p147;

public class P147 {
    private int maxn = 1000;
    int a[] = new int[maxn];
    int n;

    // 辅助函数，求数据的最大位数
    int maxbit(int data[], int n) {
        int d = 1; // 统计最大的位数
        int p = 10;
        for (int i = 0; i < n; i++) {
            while (data[i] >= p) {
                p *= 10;
                ++d;
            }
        }
        return d;
    }

    // 基数排序
    void radixsort(int data[], int n) {
        int d = maxbit(data, n); // 求最大位数
        int tmp[] = new int[n]; // 辅助数组
        int count[] = new int[10]; // 计数器数组
        int i, j, k;
        int radix = 1;
        for (i = 1; i <= d; i++) // 进行 d 次排序
        {
            for (j = 0; j < 10; j++)
                count[j] = 0; // 每次分配前清空计数器
            for (j = 0; j < n; j++) {
                k = (data[j] / radix) % 10; // 取出个位数，然后是十位数，...
                count[k]++; // 统计每个桶中的记录数
            }
            for (j = 1; j < 10; j++)
                count[j] += count[j - 1]; // 将 tmp 中的位置依次分配给每个桶
            for (j = n - 1; j >= 0; j--) // 将所有桶中记录依次收集到tmp中
            {
                k = (data[j] / radix) % 10;
                tmp[--count[k]] = data[j];
            }
            for (j = 0; j < n; j++) // 将临时数组的内容复制到data中
                data[j] = tmp[j];
            output += "第" + i + "次排序结果：\n";
            for (int m = 0; m < n; m++)
                output += data[m] + "\t";
            output += "\n";
            radix = radix * 10;
        }
    }

    public String output = "";

    public String cal(String input) {
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]); // 第 1 行为待排序的关键字的个数
        String[] num = line[1].split(" "); // 第 2 行为排序关键字序列
        for (int i = 0; i < n; i++)
            a[i] = Integer.parseInt(num[i]);
        radixsort(a, n);
        return output;
    }
}
